package test;

import javax.swing.tree.TreeNode;
import java.util.*;

public class sort {
    static int  ans=0;
    public static void main(String[] args) {





    }
    public static int mg (int a,int b,int [][]n) {
       int [][]bishu = new int[a+1][b+1];
       bishu[1][1] = 1;
       for(int i=1;i<=a;i++) {
           for(int j=1;j<=b;j++) {
               if(i==1){
                   bishu[i][j] = bishu[i][j-1]+n[i-1][j-1];}
               else if(j==1)
               {bishu[i][j] = bishu[i-1][j]+n[i-1][j-1];}
               else
               {bishu[i][j]=Math.min(bishu[i-1][j]+n[i-1][j-1],bishu[i][j-1]+n[i-1][j-1]);}
           }
       }
       return bishu[a+1][b+1];
    }
    public static String reverseString(String s) {
        if (s == null || s.length() == 0){
            return "";
        }
       StringBuilder sb=new StringBuilder(s);
        return sb.reverse().toString();
    }
    public static int[] twoSum(int[] nums, int target) {
        int r,l=0;
        for ( l = 0; l < nums.length; l++) {
            for ( r = l+1; r < nums.length; r++) {
               if (nums[l] + nums[r] == target) {
                   return new int[]{l,r};
               }
            }
        }
        return null;
    }
    public static int[] twoSum1(int[] nums, int target) {
        Map<Integer,Integer> maplist=new HashMap<>() ;
            for(int i =0;i<nums.length;i++){
                int l=target-nums[i];
                if(maplist.containsKey(l)){
                    return new int[]{maplist.get(l),i};
                }
                maplist.put(nums[i],i);
            }
        return null;
    }
    public static void moveZeroes(int[] nums) {
        // 实现代码
       int index= 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index] = nums[i];
                index++;}
        }
        for (int j = index; j <nums.length ; j++) {
            nums[j] = 0;
        }
    }

//链表
    public class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    public class LinkList{
        ListNode head;
        public void add(ListNode l){
            if(head==null){
                head=l;
            }else{
                ListNode p=head;
                while(p.next!=null){
                    p=p.next;
                }p.next=l;
            }
        }
        public void print(){
            ListNode p=head;
            while(p.next!=null){
                p=p.next;
                System.out.print(p.val + " ");
            }
            System.out.println(p.val);
        }
    }
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val=val;
            this.left=null;
            this.right=null;
        }
    }
    public class Tree{
        TreeNode root;
        public Tree(int val) {
        }
        private TreeNode add(TreeNode  p, int val) {
            if(p==null){
                p=new TreeNode(val);
            }
            if(val<p.val){
                p.left=add(p.left,val);
            } else if (val>p.val) {
                p.right=add(p.right,val);
            }
            return p;
        }

    }

    public int stl(int num){
        HashMap<Character,Integer>numlist=new HashMap<>();
        String s=String.valueOf(num);
        for(char c:s.toCharArray()){
            if(numlist.containsKey(c)){
                if(numlist.get(c)>c-'0'){
                    numlist.remove(c);
                }else
                    numlist.put(c,numlist.get(c)+1);
            }else numlist.put(c,1);
        }
        return 0;
    }//求解全排列
   public List<List<Integer>>quanpailie ( int[] nums) {
       List<List<Integer>> numlist=new ArrayList<>();
        boolean []used=new boolean[nums.length];
        List<Integer> path=new ArrayList<>();
       dfs(nums, numlist,used, path);
       return numlist;
   }
   public void dfs(int []nums,List<List<Integer>> numlist,boolean []used,List<Integer> path){
        if(path.size()==nums.length){
            numlist.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!used[i]){
                path.add(nums[i]);
                used[i]=true;
                dfs(nums,numlist,used,path);
                used[i]=false;
                path.remove(path.size()-1);
            }
        }
   }

}
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < arr[mid + 1]) {
                l = mid + 1;  // 峰值在右边
            } else {
                r = mid;  // 峰值在 mid 或左边
            }
        }
        return l;  // 当 l == r 时，找到了峰值的索引
    }




}
